#include <iostream>
#include <vector>
using namespace std;

/**
 * 排序排序是一种不稳定的排序，例如对于序列 [5, 8, 5, 2, 9]，第一次会将 5 与 2
 * 的顺序进行交互
 * 打破了序列中两个 5 的相对位置
 */
class SelectionSort {
public:
  static void selectionSort(vector<int> &v) {
    int temp = 999;
    for (int i = 0; i < v.size(); ++i) {
      // minIndex: 用来记录未排序序列的最小值
      int minIndex = i;
      for (int j = i + 1; j < v.size(); ++j) {
        if (v[j] < v[minIndex]) {
          minIndex = j;
        }
      }
      temp = v[minIndex];
      v[minIndex] = v[i];
      v[i] = temp;
    }
  }
};

int main() {
  vector<int> v{5, 100, 5, 14, 3};
  SelectionSort::selectionSort(v);
  for (auto &i : v) {
    cout << i << " ";
  }
  cout << endl;

  return 0;
}